In data processing systems single or multiple bit errors may occur to affect the validity of the data which is being processed therein. Such data errors may arise in the memory storage system of such data processors and have been found to arise particularly when semiconductor memory devices are being utilized.
In systems having relatively low data storage capacity, e.g., in data processing systems which are often referred to as "minicomputers", such systems often having storage capacities as low as 32K words or less, the problems of data integrity often have not been considered as important as data errors which are likely to occur in systems having much larger storage capacities. However, as minicomputers utilize larger and larger storage capacities, sometimes extending the storage capacity to as high as 128K words or more, and are used in a larger variety of applications, the problem of data errors, particularly single bit data errors, has begun to require the attention of designers and manufacturers thereof.
In systems which detect single bit errors, the error correction techniques which may be employed often depend on the particular application in which the data processing system is being utilized. For example, where such computers are used in controlling manufacturing processes on a production line and the presence of a single bit error may be extremely harmful, the overall production line may often have to be shut down completely while the error is corrected in some appropriate manner. Since such shut-downs are costly and time consuming, it is desirable to be able not only to detect the errors but also to correct them substantially immediately.
In other applications where an error has been detected during the implementation of a particular software program, the approach has often been to correct the error and to re-run the entire program from the beginning once again. In applications wherein the program run is a long one, e.g., where the program may run for several days, such a re-run procedure utilizes valuable time so that it is desirable to be able to detect and to correct errors promptly in order to avoid the time loss as well as the re-run costs that may be incurred.
In relatively large capacity computers, error detection is often implemented through the use of conventional parity checks. Such conventional parity check procedures, however, do not detect all of the single bit errors which may occur and, further, even for those single bit errors which are detected, parity check techniques do not provide for any correction thereof. In using conventional parity check procedures, further techniques must be devised for the correction of errors and, to this end, it has been suggested that Hamming codes be utilized in conjunction with parity checks to provide a direct address of the error location so that correction thereof can be made. The primary problem in utilizing conventional Hamming codes for producing direct address information lies in the fact that too many Hamming code terms are needed to provide suitable address identification. For example, in using normal Hamming code techniques, with a 16-bit data word, up to 11 to 12 terms effectively representing 11 or 12 bits of the data word are required to be processed by a single logic element (i.e., an exclusive-OR element) in the implementation of Hamming code procedures. In the present state of the art, however, logic elements having more than 9 inputs at most are not available and in order to implement conventional Hamming code techniques, specially designed logic elements must be made for such use which designs undesirably increase the cost of manufacture of the error detection and correction system. Such cost increase is particularly disadvantageous in minicomputer systems where such costs are an important competition consideration. Hence, the use of conventional Hamming codes to provide direct address information has usually been avoided except in relatively large capacity systems.